package leetcode.datastruct1;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;


/**
 * RandomizedCollection 是一种包含数字集合(可能是重复的)的数据结构。它应该支持插入和删除特定元素，以及删除随机元素。
 *
 * 实现 RandomizedCollection 类:
 *
 * RandomizedCollection()初始化空的 RandomizedCollection 对象。
 * bool insert(int val) 将一个 val 项插入到集合中，即使该项已经存在。如果该项不存在，则返回 true ，否则返回 false 。
 * bool remove(int val) 如果存在，从集合中移除一个 val 项。如果该项存在，则返回 true ，否则返回 false 。注意，如果 val 在集合中出现多次，我们只删除其中一个。
 * int getRandom() 从当前的多个元素集合中返回一个随机元素。每个元素被返回的概率与集合中包含的相同值的数量 线性相关 。
 * 您必须实现类的函数，使每个函数的 平均 时间复杂度为 O(1) 。
 *
 * 注意：生成测试用例时，只有在 RandomizedCollection 中 至少有一项 时，才会调用 getRandom 。
 *
 *
 *
 * 示例 1:
 *
 * 输入
 * ["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"]
 * [[], [1], [1], [2], [], [1], []]
 * 输出
 * [null, true, false, true, 2, true, 1]
 *
 * 解释
 * RandomizedCollection collection = new RandomizedCollection();// 初始化一个空的集合。
 * collection.insert(1);   // 返回 true，因为集合不包含 1。
 *                         // 将 1 插入到集合中。
 * collection.insert(1);   // 返回 false，因为集合包含 1。
 *                         // 将另一个 1 插入到集合中。集合现在包含 [1,1]。
 * collection.insert(2);   // 返回 true，因为集合不包含 2。
 *                         // 将 2 插入到集合中。集合现在包含 [1,1,2]。
 * collection.getRandom(); // getRandom 应当:
 *                         // 有 2/3 的概率返回 1,
 *                         // 1/3 的概率返回 2。
 * collection.remove(1);   // 返回 true，因为集合包含 1。
 *                         // 从集合中移除 1。集合现在包含 [1,2]。
 * collection.getRandom(); // getRandom 应该返回 1 或 2，两者的可能性相同。
 *
 *
 * 提示:
 *
 * -231 <= val <= 231 - 1
 * insert, remove 和 getRandom 最多 总共 被调用 2 * 105 次
 * 当调用 getRandom 时，数据结构中 至少有一个 元素
 */
public class LeetCode381_RandomizedSetDuplicated {

    private Map<Integer, List<Integer>> rSet = new HashMap<>();
    private List<Integer> rArr = new ArrayList<>();

    public LeetCode381_RandomizedSetDuplicated() {

    }

    public boolean insert(int val) {
        // 重复下标集合
        List<Integer> idxs;

        int index = rArr.size();
        rArr.add(index, val);

        if (rSet.containsKey(val)) {
            idxs = rSet.get(val);
            idxs.add(index);
            return false;
        }else {
            idxs = new ArrayList<>();
            idxs.add(index);
            rSet.put(val, idxs);
            return true;
        }
    }

    public boolean remove(int val) {
        if (!rSet.containsKey(val)) {
            return false;
        }
        List<Integer> idxs = rSet.get(val);
        Integer dupIndex = idxs.get(0);
        Integer endValue = rArr.get(rArr.size() - 1);
        if (val == endValue) {
            idxs.removeIf(v -> v == rArr.size() - 1);
        }else {
            List<Integer> paddingIdxs = rSet.get(endValue);
            paddingIdxs.add(dupIndex);
            paddingIdxs.removeIf(v -> v == rArr.size() - 1);
            rArr.set(dupIndex, endValue);
            idxs.remove(0);
        }
        rArr.remove(rArr.size() - 1);
        // 元素都删除完了
        if (idxs.isEmpty()) {
            rSet.remove(val);
        }
        return true;
    }

    public int getRandom() {
        return rArr.get((int) (Math.random() * rArr.size()));
    }

    public static void main(String[] args) {
        LeetCode381_RandomizedSetDuplicated leetCode381RandomizedSet = new LeetCode381_RandomizedSetDuplicated();
        leetCode381RandomizedSet.insert(4);
        leetCode381RandomizedSet.insert(3);
        leetCode381RandomizedSet.insert(4);
        leetCode381RandomizedSet.insert(2);
        leetCode381RandomizedSet.insert(4);
        leetCode381RandomizedSet.remove(4);
        leetCode381RandomizedSet.remove(3);
        leetCode381RandomizedSet.remove(4);
        leetCode381RandomizedSet.remove(4);
    }
}
